// 给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。
//
// 一个子数组指的是原数组中连续的一个子序列。 
//
// 请你返回满足题目要求的最短子数组的长度。 
//
// 
//
// 示例 1： 
//
// 
//输入：arr = [1,2,3,10,4,2,3,5]
//输出：3
//解释：我们需要删除的最短子数组是 [10,4,2] ，长度为 3 。剩余元素形成非递减数组 [1,2,3,3,5] 。
//另一个正确的解为删除子数组 [3,10,4] 。 
//
// 示例 2： 
//
// 
//输入：arr = [5,4,3,2,1]
//输出：4
//解释：由于数组是严格递减的，我们只能保留一个元素。所以我们需要删除长度为 4 的子数组，要么删除 [5,4,3,2]，要么删除 [4,3,2,1]。
// 
//
// 示例 3： 
//
// 
//输入：arr = [1,2,3]
//输出：0
//解释：数组已经是非递减的了，我们不需要删除任何元素。
// 
//
// 示例 4： 
//
// 
//输入：arr = [1]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= arr.length <= 10^5 
// 0 <= arr[i] <= 10^9 
// 
// Related Topics 栈 数组 双指针 二分查找 单调栈 
// 👍 48 👎 0


package cn.db117.leetcode.solution15;

/**
 * 1574.删除最短的子数组使剩余数组有序.shortest-subarray-to-be-removed-to-make-array-sorted
 *
 * @author db117
 * @since 2021-07-20 14:42:26
 **/

public class Solution_1574 {
    public static void main(String[] args) {
        Solution solution = new Solution_1574().new Solution();

        System.out.println(solution.findLengthOfShortestSubarray(new int[]{
                1, 2, 3, 10, 4, 2, 3, 5
        }));
        System.out.println(solution.findLengthOfShortestSubarray(new int[]{
                5, 4, 3, 2, 1
        }));
        System.out.println(solution.findLengthOfShortestSubarray(new int[]{
                1, 2, 3
        }));
        System.out.println(solution.findLengthOfShortestSubarray(new int[]{
                1
        }));
        System.out.println(solution.findLengthOfShortestSubarray(new int[]{
                1, 2, 3, 10, 0, 7, 8, 9
        }));// 2
        System.out.println(solution.findLengthOfShortestSubarray(new int[]{
                6, 3, 10, 11, 15, 20, 13, 3, 18, 12
        }));// 8
        System.out.println(solution.findLengthOfShortestSubarray(new int[]{
                5002, 5282, 611, 160, 4040, 3834, 8644, 1127, 3052, 1908, 8153, 8677, 2307, 3877, 3159, 7785, 2009, 3005, 7135, 1040, 6277, 742, 312, 9209, 59, 7729, 6107, 1046, 6657, 4499, 4510, 2318, 5692, 3017, 1558, 553, 733, 1753, 1440, 4748, 4696, 3980, 7227, 4291, 3174, 1668, 8432, 1923, 4790, 112, 1477, 6271, 2358, 854, 2022, 6257, 889, 4204, 5793, 1067, 3194, 1829, 5964, 297, 3162, 167, 1705, 8971, 7595, 6387, 4191, 886, 8124, 8951, 8401, 8579, 6845, 7317, 6593, 7148, 4392, 8469, 7390, 6499, 108, 4478, 4609, 76, 658, 7961, 1177, 412, 7540, 4510, 2424, 3220, 7121, 2195, 1178, 4963, 7664, 6299, 6260, 2550, 7954, 1505, 6071, 6617, 619, 3503, 6712, 274, 6504, 1569, 2649, 8682, 5594, 8639, 4395, 2780, 8655, 1387, 4495, 3564, 4266, 8190, 1389, 3737, 3564, 6985, 5237, 9140, 286, 5005, 2800, 5735, 543, 4472, 6958, 8974, 3552, 4479, 3012, 3971, 2680, 5257, 823, 9141, 4118, 5310, 8639, 4802, 4691, 3363, 6792, 7127, 8654, 7723, 8709, 8794, 953, 3807, 2670, 5487, 2069, 582, 5554, 6865, 5765, 6654, 8588, 3115, 5698, 5929, 6835, 4226, 6084, 352, 2667, 3898, 8334, 4896, 1022, 4310, 7153, 3596, 3531, 4788, 2611, 1137, 3249, 5530, 7223, 2574, 8233, 7155, 1342, 8142, 4778, 4634, 9140, 1070, 4372, 9213, 3256, 4318, 724, 4814, 5682, 6466, 6648, 5279, 2201, 5073, 5726, 6980, 759, 3372, 827, 6834, 621, 5591, 17, 4393, 8336, 2780, 2693, 1959, 2062, 5869, 7872, 4892, 761, 4809, 3552, 3603, 962, 911, 4267, 3551, 6785, 1552, 4162, 2974, 5356, 1782, 1366, 1385, 785, 4188, 7551, 2361, 1314, 6946, 5974, 469, 8022, 7700, 4515, 3818, 6866, 5150, 850, 5013, 6786, 8669, 6421, 1216, 4574, 5547, 2211, 4399, 647, 4671, 624, 5931, 3172, 4667, 6627, 4620, 7772, 8384, 6443, 6962, 2019, 8987, 5693, 8937, 5810, 4902, 1407, 2028, 7603, 2309, 637, 2701, 4503, 3216, 6387, 7470, 3470, 2486, 4363, 5558, 7560, 4252, 6410, 6938, 6961, 13, 2828, 596, 152, 3381, 261, 6769, 8267, 7724, 7113, 1908, 3125, 1269, 8093, 1487, 6073, 8641, 5982, 3256, 4689, 6980, 3340, 7059, 5178, 4215, 5917, 6383, 1770, 7404, 29, 2222, 3179, 206, 7565, 8573, 2406, 3854, 6346, 6160, 2813, 8981, 2799, 5153, 3227, 7350, 5876, 4314, 1998, 9137, 7233, 9173, 5149, 4849, 2994, 5363, 7296, 3671, 8865, 6486, 2197, 2429, 5194, 2521, 5608, 4590, 999, 1760, 42, 413, 4189, 6079, 1804, 5961, 1863, 9198, 8154, 3991, 4448, 3236, 1450, 1616, 8675, 900, 7578, 4226, 1702, 8603, 4359, 1744, 5956, 8508, 240, 50, 589, 3893, 8886, 2532, 7401, 8798, 8853, 3873, 8172, 6731, 3303, 5010, 4334, 664, 7683, 3735, 6135, 5026, 895, 5998, 433, 8001, 8002, 6183, 2488, 5843, 5201, 7412, 640, 5164, 3610, 928, 6583, 945, 2959, 2408, 3033, 4310, 9078, 6223, 2705, 3297, 2605, 3764, 2514, 5295, 9203, 4064, 2563, 6193, 9291, 1841, 2370, 5272, 7130, 3981, 2586, 4885, 2214, 1600, 8322, 5451, 1466, 5678, 3414, 8735, 433, 8266, 5051, 9146, 2560, 1388, 4665, 2734, 6792, 7708, 3266, 270, 3258, 6180, 8182, 7475, 242, 4322, 8204, 8152, 1651, 6994, 7916, 7560, 3836, 1163, 3733, 371, 8312, 5527, 8956, 6916, 4302, 3445, 7063, 1132, 5637, 1519, 1247, 1388, 2937, 2645, 8746, 8046, 7954, 6060, 955, 5344, 2629, 2167, 4778, 6997, 8570, 526, 4221, 6423, 6319, 1077, 9216, 804, 2223, 7477, 2553, 1632, 68, 2563, 4414, 8315, 2265, 8185, 5606, 268, 4137, 3246, 3702, 5695, 2609, 7340, 8767, 6867, 7702, 8433, 225, 2293, 2070, 7110, 1628, 6864, 7883, 1489, 7388, 2150, 8411, 6007, 1001, 7680, 5085, 4009, 7222, 3128, 7870, 8568, 788, 7861, 4028, 7163, 2994, 1028, 3408, 5382, 6920, 3274, 1731, 2971, 4080, 4797, 1444, 6043, 7591, 7772, 4624, 7684, 585, 6214, 5744, 5819, 2207, 646, 3574, 1031, 7311, 330, 982, 8693, 5193, 1149, 2084, 9020, 303, 8759, 5799, 6183, 390, 7148, 4007, 1640, 8823, 8149, 9011, 6274, 3366, 2271, 885, 7992, 113, 4940, 1428, 4898, 1533, 8746, 838, 8958, 9292, 3149, 3321, 6392, 7699, 36, 3700, 408, 854, 8124, 1900, 8220, 9021, 4377, 6660, 7202, 3915, 3882, 5859, 6705, 665, 1216, 5666, 5662, 6460, 8264, 2706, 6962, 2564, 200, 2438, 5757, 5304, 7351, 3715, 5605, 7252, 6494, 4115, 6575, 7355, 4126, 3649, 4173, 5975, 5164, 1157, 569, 2596, 2041, 5482, 8428, 3987, 3841, 5581, 5151, 3341, 1693, 393, 1318, 2738, 4956, 5252, 4338, 9074, 1534, 3872, 6296, 5609, 7283, 2673, 6191, 3126, 3669, 5378, 9016, 3988, 2024, 764, 5287, 6931, 1134, 5522, 2845, 3209, 126, 21, 4915, 4840, 6176, 7723, 5529, 5241, 7788, 7588, 629, 3083, 5542, 7159, 7595, 4388, 5062, 619, 2145, 6627, 4951, 8064, 7446, 6073, 4420, 7295, 4843, 9135, 7372, 6467, 2257, 7846, 655, 7964, 887, 5465, 2468, 2513, 590, 1443, 6530, 8723, 8457, 2733, 3284, 3493, 2110, 7573, 7831, 9077, 385, 4148, 3246, 2513, 5959, 3683, 8279, 748, 2139, 6750, 3179, 2753, 6, 5025, 2839, 1106, 3804, 85, 6082, 3576, 860, 3144, 7085, 9062, 7566, 2400, 3679, 1736, 3875, 3021, 3904, 2957, 33, 9305, 6194, 4353, 2952, 3337, 4446, 5741, 2068, 5246, 2008, 6473, 3574, 1310, 6544, 1915, 439, 9290, 8341, 1419, 7215, 5130, 3633, 3255, 1282, 1226, 8004, 2080, 3784, 8935, 1097, 7216, 4477, 2372, 8425, 7879, 1304, 7166, 6613, 9239, 333, 3590, 9290, 2021, 2612, 2723, 3457, 8211, 7815, 8765, 2963, 2728, 3912, 7722, 1020, 3644, 4673, 2887, 7105, 1099, 9066, 7454, 1446, 7751, 6465, 2641, 1457, 2194, 3116, 5470, 4180, 7044, 9264, 4249, 965, 5730, 7411, 1363, 5864, 2912, 3754, 4779, 5914, 3637, 3236, 9304, 7836, 5913, 2341, 4841, 414, 243, 9100, 1701, 5159, 2979, 4805, 5553, 2375, 4541, 7933, 8360, 3733, 832, 4158, 8414, 582, 4946, 8046, 8667, 987, 4143, 1573, 1941, 117, 2479, 9202, 3987, 3527, 2274, 6611, 7020, 268, 7137, 3936, 2662, 3448, 3934, 1000, 8438, 6041, 7220, 4699, 7983, 8340
        }));// 928
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findLengthOfShortestSubarray(int[] arr) {
            // 先找左边非递减
            int left = 0;
            while (left + 1 < arr.length && arr[left + 1] >= arr[left]) {
                left++;
            }
            if (left == arr.length - 1) {
                // 全部非递减
                return 0;
            }

            // 再找右边非递减
            int right = arr.length - 1;
            while (right - 1 > 0 && arr[right - 1] <= arr[right]) {
                right--;
            }

            // 合并
            if (arr[left] <= arr[right]) {
                // 两边数组没有冲突
                return right - left - 1;
            }

            // 需要解决冲突
            // 保留最长的数组
            int ans = Math.min(right, arr.length - left - 1);

            int leftMax = left;
            left = 0;
            // 固定右边界，尽量缩小左边界
            while (left <= leftMax && right < arr.length) {
                if (arr[left] <= arr[right]) {
                    // 符合题意找最值
                    ans = Math.min(ans, right - left - 1);
                    // 移动左边界
                    left++;
                } else {
                    // 移动有边界
                    right++;
                }
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}